package selected;

import java.util.*;

public class J0828 {
    // 1.岛屿数量
    boolean[][] vis = new boolean[301][301];
    int m, n;
    int[] dx = {0, 0, -1, 1};
    int[] dy = {1, -1, 0, 0};
    public int numIslands(char[][] grid) {
        int ret = 0;
        m = grid.length; n = grid[0].length;
        for(int i = 0; i < m; i++){
            for(int j = 0; j < n; j++){
                if(grid[i][j] == '1' && !vis[i][j]){
                    ret++;
                    bfs(grid, i, j);
                }
            }
        }
        return ret;
    }
    public void bfs(char[][] grid, int i, int j){
        Queue<int[]> queue = new LinkedList<>();
        queue.offer(new int[]{i, j});
        while(!queue.isEmpty()){
            int[] t = queue.poll();
            int a = t[0], b = t[1];
            for(int k = 0; k < 4; k++){
                int x = a + dx[k], y = b + dy[k];
                vis[a][b] = true;
                if(x < m && x >= 0 && y < n && y >= 0
                        && grid[x][y] == '1' && !vis[x][y]){
                    queue.offer(new int[]{x, y});
                    vis[x][y] = true;
                }
            }
        }
    }
    // 2.腐烂的橘子
    public int orangesRotting(int[][] grid) {
        int m = grid.length, n = grid[0].length;
        int fresh = 0, time = 0;
        int[] dx = {1, -1, 0, 0};
        int[] dy = {0, 0, -1, 1};
        Queue<int[]> queue = new LinkedList<>();
        for(int i = 0; i < m; i++){
            for(int j = 0; j < n; j++){
                if(grid[i][j] == 1) fresh++;
                if(grid[i][j] == 2) queue.offer(new int[]{i, j});
            }
        }
        // 进行广搜
        while(!queue.isEmpty()){
            int size = queue.size();
            // 加一个被感染的标志位，最后一轮应当是没有发生感染的，所以不会走if中的语句，若单纯的执行time++则会多一次
            boolean infection = false;
            while(size-- > 0){
                int[] t = queue.poll();
                int a = t[0], b = t[1];
                for(int k = 0; k < 4; k++){
                    int x = a + dx[k];
                    int y = b + dy[k];
                    if(x >= 0 && x < m && y >= 0 && y < n && grid[x][y] == 1){
                        grid[x][y] = 2;
                        queue.offer(new int[]{x, y});
                        fresh--;
                        infection = true;
                    }
                }
            }
            if(infection) time++;
        }
        if(fresh == 0) return time;
        else return -1;
    }
    // 3.课程表
    public boolean canFinish(int num, int[][] p) {
        // 使用拓扑排序 + bfs
        int m = p.length;
        int[] input = new int[num];
        // 建图
        Map<Integer, List<Integer>> map = new HashMap<>();
        for(int i = 0; i < m; i++){
            int a = p[i][0], b = p[i][1];
            if(!map.containsKey(b)){
                map.put(b, new ArrayList<Integer>());
            }
            map.get(b).add(a);
            input[a]++;
        }

        // 遍历数组找出入度为0的数加入拓扑序列中
        Queue<Integer> queue = new LinkedList<>();
        for(int i = 0; i < num; i++){
            // 这里要加入的是i，也就是课程，而input[i] 中存储的是 i 的入度值
            if(input[i] == 0) queue.offer(i);
        }
        // bfs
        while(!queue.isEmpty()){
            int t = queue.poll();
            // 删除这个点
            // 也就是这个顶点所连接的其他顶点入度 -1
            for(int i : map.getOrDefault(t, new ArrayList<Integer>())){
                if(--input[i] == 0) queue.offer(i);
            }
        }
        for(int i : input){
            if(i != 0) return false;
        }
        return true;
    }
    // 4.全排列
    List<List<Integer>> ret;
    List<Integer> path;
    boolean[] check;

    public List<List<Integer>> permute(int[] nums) {
        ret = new ArrayList<>();
        path = new ArrayList<>();
        check = new boolean[nums.length];
        dfs(nums);
        return ret;
    }
    public void dfs(int[] nums){
        if(path.size() == nums.length){
            // 这里要创建一个新的链表放进ret中，因为path是一个引用变量
            // 若这里添加path，当dfs结束时path为空，所有的结果都会被清空
            ret.add(new ArrayList<>(path));
            return;
        }

        for(int i = 0; i < nums.length; i++){
            if(check[i] == false){
                path.add(nums[i]);
                check[i] = true;
                dfs(nums);
                // 回溯
                check[i] = false;
                path.remove(path.size() - 1);
            }
        }
    }
}
